
#include "UTSCImpl.hpp"
#include <functional>
#include <stack>
#include <algorithm>
using namespace NNU::UTSC;
using namespace NNU::UTSC::Kernel;
using namespace NNU::UTSC::Kernel::Time;


/*************************************接口函数实现**************************************************/
void UTSCImpl::init() {
}

void UTSCImpl::release() {
}

/// <summary>
/// 编码（时间点）
/// </summary>
/// <param name="time"></param>
/// <param name="code"></param>
/// <returns></returns>
bool UTSCImpl::encode(NNU::UTSC::UTSCTime *time, NNU::UTSC::UTSCElementCode *&code) {
	int i = 0;
	// 遍历时间片段
	while (time->segmentTime[i].elementType != UTSCElementType::Unknown && i < time->size)
	{
		//判断时间单位（年、月、日等）
		UTSCElementType Time_type = time->segmentTime[i].elementType;
		assignCode(code, time, static_cast<uint8_t>(Time_type), UTSCElementTypeMap[Time_type], i);
		++i;
	}
	return 1;
}

/// <summary>
/// 解码（时间点）
/// </summary>
/// <param name="code"></param>
/// <param name="time"></param>
/// <returns></returns>
bool UTSCImpl::decode(NNU::UTSC::UTSCElementCode *code, NNU::UTSC::UTSCTime *&time) 
{
	int i = 0;

	//判断时间系统
	if (code->segmentCode[0].params == M_Gyr_parm || code->segmentCode[0].params == M_Myr_parm || code->segmentCode[0].params == M_kyr_parm)
		time->system = UTSCTimeSystemType::Geo;
	else
		time->system = UTSCTimeSystemType::UTC;

	// 遍历时间编码各片段
	while (code->segmentCode[i].params != M_unknown_parm && i < code->size)
	{
		uint8_t temp_base = (code->segmentCode[i].params >> M_BitMove) & 0x0F;
		uint16_t temp_code = code->segmentCode[i].codes;
		assignTimeInfo(time, code->signal, temp_code, temp_base, i);
		++i;
	}
	return 1;
}


// 辅助：切出与 lo/hi 一致长度的 order 片段
static inline std::vector<UTSCElementType>
sliceOrder(const std::vector<UTSCElementType>& order, size_t len) {
    len = std::min(len, order.size());
    return std::vector<UTSCElementType>(order.begin(), order.begin() + (ptrdiff_t)len);
}


/// <summary>
/// 编码（时间范围）
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
/// <param name="out"></param>
/// <returns></returns>
bool UTSCImpl::encode(UTSCTime* start, UTSCTime* end, std::vector<UTSCElementCode>& out) {
    out.clear();
    if (!start || !end) return false;
    if (start->system != end->system) return false;

    UTSCTimeSystemType sys = start->system;
    std::vector<UTSCElementType> order; getUnitOrder(sys, order);

    // 计算两个时间的实际最低精度
    int sPrec = start->size - 1;
    int ePrec = end->size - 1;
    int minPrec = std::min(sPrec, ePrec);

    // 基础 cutOrder（用于“全长”场景）
    std::vector<UTSCElementType> cutOrder(order.begin(), order.begin() + minPrec + 1);

    // 取值与“是否有值”
    std::vector<int>  sv, ev;
    std::vector<bool> sHave, eHave;
    normalizeToOrder(start, cutOrder, sv, sHave);
    normalizeToOrder(end,   cutOrder, ev, eHave);

    // 精度对齐（低精度 → min / max）
    fillLowHigh(sys, cutOrder, sv, sHave, ev, eHave);

    // 若完全相同（同一个时间点范围）
    if (sv == ev) {
        UTSCElementCode* single = new UTSCElementCode(M_Type_number);
        this->encode(start, single);
        out.push_back(*single);
        delete single;
        return true;
    }

    // ========== Step 2: 判断最高精度是否相同 ==========
    int idxLast = (int)cutOrder.size() - 1;

    UTSCElementType startLastUnit = start->segmentTime[sPrec].elementType;
    UTSCElementType endLastUnit   = end->segmentTime[ePrec].elementType;

    if (startLastUnit == endLastUnit) {

        // 2.1.1 最高精度相同 + 前缀是否一致
        bool prefixEqual = true;
        for (int i = 0; i < idxLast; i++) {
            if (sv[i] != ev[i]) { prefixEqual = false; break; }
        }
        if (prefixEqual) {
            // 2.1.1.1 尝试单节点覆盖
            if (trySingleNodeEncode(sys, cutOrder, sv, ev, out)) {
                return true;
            }
            // 2.1.1.2 用 dyadic 分割覆盖整个范围（full cutOrder）
            std::vector<int> cur = sv;
            while (compareTuple(cur, ev) <= 0) {
                int k = findLargestDyadic(sys, cutOrder, cur, ev);
                std::vector<int> prefix(cur.begin(), cur.begin() + k);
                int lo = cur[k];
                int hi = std::min(ev[k], unitMaxWithPrefix(sys, cutOrder, cur, k));
                emitUnitRange(sys, cutOrder, prefix, k, lo, hi, out);

                // 推进 cur
				cur[k] = hi + 1;
				if (cur[k] > unitMaxWithPrefix(sys, cutOrder, cur, k)) {
					break; // 当前层已经覆盖完成，退出循环
				}
            }
            return true;
        }
        else {
            // 2.1.2 最高精度相同但低层不同 → 插虚拟时间点（可能“截断”到更高层）
            std::vector<std::pair<std::vector<int>, std::vector<int>>> subRanges;
            makeVirtualRanges(sys, cutOrder, sv, ev, subRanges);

            for (auto& rng : subRanges) {
                // —— 对齐每个子片段的长度（避免 vector 越界）
                size_t L = std::min(rng.first.size(), rng.second.size());
                if (L == 0) continue;

                std::vector<UTSCElementType> localOrder = sliceOrder(cutOrder, L);
                std::vector<int> lo = rng.first;  lo.resize(L);
                std::vector<int> hi = rng.second; hi.resize(L);

                std::vector<UTSCElementCode> subOut;
                if (trySingleNodeEncode(sys, localOrder, lo, hi, subOut)) {
                    // 单节点即可覆盖
                    out.insert(out.end(), subOut.begin(), subOut.end());
                    continue;
                }

                // dyadic 分割（按局部层级进行）
                std::vector<int> cur = lo;
                while (compareTuple(cur, hi) <= 0) {
                    int k = findLargestDyadic(sys, localOrder, cur, hi);
                    std::vector<int> prefix(cur.begin(), cur.begin() + k);
                    int vlo = cur[k];
                    int vhi = std::min(hi[k], unitMaxWithPrefix(sys, localOrder, cur, k));
                    emitUnitRange(sys, localOrder, prefix, k, vlo, vhi, out);

                    // 推进 cur（使用 localOrder 的维度）
                    cur[k] = vhi + 1;
					if (cur[k] > unitMaxWithPrefix(sys, cutOrder, cur, k)) {
						break; // 当前层已经覆盖完成，退出循环
					}
                }
            }
            return true;
        }
    }
    else {
        // 2.2 精度不同 → 填补到同一精度
        std::vector<int> sv2 = sv, ev2 = ev;
        if (sPrec < ePrec) {
            for (int j = sPrec + 1; j <= ePrec; j++) {
                sv2.push_back(unitMin(order[j]));
            }
            ev2.resize(sv2.size());
        }
        else if (ePrec < sPrec) {
            for (int j = ePrec + 1; j <= sPrec; j++) {
                ev2.push_back(unitMaxWithPrefix(sys, order, ev2, j));
            }
            sv2.resize(ev2.size());
        }

        UTSCTime s2, e2;
        s2.system = e2.system = sys;
        s2.size = (int)sv2.size();
        e2.size = (int)ev2.size();

        for (int i = 0; i < s2.size; i++) s2.setData(i, order[i], sv2[i]);
        for (int i = 0; i < e2.size; i++) e2.setData(i, order[i], ev2[i]);

        return this->encode(&s2, &e2, out);
    }
}

/// <summary>
/// 解码（时间范围）
/// </summary>
/// <param name="codes"></param>
/// <param name="start"></param>
/// <param name="end"></param>
/// <returns></returns>
// decode: 将所有 codes 分别解为 min/time 对，取 overall min 和 overall max
bool UTSCImpl::decode(std::vector<UTSCElementCode> const& codes,
	UTSCTime*& start, UTSCTime*& end) {
	if (codes.empty()) return false;

	// decode first -> start 的最小端
	if (!start) start = new UTSCTime(M_Type_number);
	if (!decodeSingleMinMax(codes.front(), true, start)) return false;

	// decode last -> end 的最大端
	if (!end) end = new UTSCTime(M_Type_number);
	if (!decodeSingleMinMax(codes.back(), false, end)) return false;

	return true;
}

/// <summary>
/// 对时间点的层级关系查询：Parent层级查询，返回一个时间点；Children层级查询，返回两个时间点；Neighbor层级查询，返回两个时间点
/// </summary>
/// <param name="topoType">需要查询的类型</param>
/// <param name="code">查询对象</param>
/// <param name="result">查询结果</param>
/// <param name="size">查询结果中包含的时间点数量</param>
/// <returns></returns>
bool UTSCImpl::structQuery(NNU::UTSC::UTSCStructType topoType, NNU::UTSC::UTSCElementCode *code,NNU::UTSC::UTSCElementCode*&result,int &size)
{
	//父时间查询
	if (topoType == Parent)
	{
		int i = 0;
		//Geo类型时间
		if (code->segmentCode[0].params == M_Gyr_parm || code->segmentCode[0].params == M_Myr_parm || code->segmentCode[0].params == M_kyr_parm)
		{
			if (code->segmentCode[0].params == M_Gyr_parm)
				return false;
			else
			{
				result->segmentCode[0].codes = 0;
				// 取前四位并右移1位
				uint8_t front = (code->segmentCode[0].params & M_FirstFour_Bit) >>(M_BitMove + 1) ;

				// 取后四位
				uint8_t back = code->segmentCode[0].params & M_LastFour_Bit;

				// 重新组合前四位（右移后的）和后四位
				result->segmentCode[0].params = (front << M_BitMove) | back;
				result->signal = code->signal;
				result->size = 1;
			}
		}
		//UTC类时间
		else
		{
			while (code->segmentCode[i].params != M_unknown_parm && i < code->size)
			{
				++i;
			}
			if (i < 1)
				return false;
			else if (i > 1)
			{
				//取最后一个时间段之前的所有时间段作为父亲
				for (int j = 0; j < i - 1; j++)                   
				{
					result->segmentCode[j].codes = code->segmentCode[j].codes;
					result->segmentCode[j].params = code->segmentCode[j].params;
				}
				result->signal = code->signal;
				result->size = i - 1;
			}
			else
			{
				result->segmentCode[0].codes = 0;
				result->segmentCode[0].params = M_kyr_parm;
				result->signal = 0;
				result->size = 1;
			}
		}
		size = 1;
	}
	//孩子时间查询
	else if (topoType == Children)
	{
		int i = 0;
		//Geo类型时间
		if (code->segmentCode[0].params == M_Gyr_parm || code->segmentCode[0].params == M_Myr_parm || code->segmentCode[0].params == M_kyr_parm)
		{
			while (code->segmentCode[i].params != M_unknown_parm && i < code->size)
			{
				++i;
			}
			i--;
			if ((code->segmentCode[i].params == M_kyr_parm))
			{
				result[0].segmentCode[0].codes = M_Geo_Year_Min;
				result[0].segmentCode[0].params = M_Year_parm;
				result[0].signal = code->signal;
				result[0].size = 1;

				//右区间是999，如果是1000就需要进一位了
				result[1].segmentCode[0].codes = M_Geo_Year_Max;
				result[1].segmentCode[0].params = M_Year_parm;
				result[1].signal = code->signal;
				result[1].size = 1;
			}
			else
			{
				// 取前四位并递进一位（孩子的base比父亲大）
				uint8_t front = ((code->segmentCode[i].params >> 4) & M_LastFour_Bit) + 1;

				// 取后四位
				uint8_t back = code->segmentCode[i].params & M_LastFour_Bit;

				// 重新组合前四位（右移后的）和后四位
				result[0].segmentCode[0].codes = M_GeoTime_Min - 1;
				result[0].segmentCode[0].params = (front << M_BitMove) | back;
				result[0].signal = code->signal;
				result[0].size = 1;

				//右区间是999，如果是1000就需要进一位了
				result[1].segmentCode[0].codes = M_GeoTime_Max - 1 - 1;
				result[1].segmentCode[0].params = (front << M_BitMove) | back;
				result[1].signal = code->signal;
				result[1].size = 1;
			}
				
		}
		//UTC类时间
		else
		{
			while (code->segmentCode[i].params != M_unknown_parm && i < code->size)
			{
				++i;
			}
			for (int j = 0; j < i; j++)
			{
				result[0].segmentCode[j].codes = code->segmentCode[j].codes;
				result[0].segmentCode[j].params = code->segmentCode[j].params;
				result[1].segmentCode[j].codes = code->segmentCode[j].codes;
				result[1].segmentCode[j].params = code->segmentCode[j].params;
			}
			result[0].signal = code->signal;
			result[0].size = i+1;
			result[1].signal = code->signal;
			result[1].size = i+1;

			//判断该时间点的最小时间单位
			int type = (int)(code->segmentCode[i-1].params >> M_BitMove) & 0x0F;

			//如果最小时间单位为月，则需要获取年的数值来进行闰年的判断
			int preData = 0;
			if (code->signal == 1)
			{
				if ((int)code->segmentCode[i - 2].codes != M_TimeOrigin)
					preData = (int)code->segmentCode[i - 2].codes + 1 + M_TimeOrigin;
				else
					preData = M_TimeOrigin;
			}
			else
			{
				 preData = M_TimeOrigin - (int)code->segmentCode[i - 2].codes - 1;
			}
			

			//存储12月中的天数
			int monthsarray[13] = { 
				M_Feb_LeapYear_Days -1,
				M_Big_Month_Days - 1,
				M_Feb_NormalYear_Days - 1,
				M_Big_Month_Days - 1,
				M_Small_Month_Days - 1,
				M_Big_Month_Days - 1,
				M_Small_Month_Days - 1,
				M_Big_Month_Days - 1,
				M_Big_Month_Days - 1,
				M_Small_Month_Days - 1,
				M_Big_Month_Days - 1,
				M_Small_Month_Days - 1,
				M_Big_Month_Days - 1
			};
			uint8_t base = type + 1;

			switch (type)
			{
			case (int)UTSCElementType::Year:   //父亲是年
				result[0].segmentCode[i].codes = M_Month_Min - 1;
				result[0].segmentCode[i].params = (base << M_BitMove) | M_Month_Level;
				result[1].segmentCode[i].codes = M_Month_Max - 1;
				result[1].segmentCode[i].params = (base << M_BitMove) | M_Month_Level;
				break;
			case (int)UTSCElementType::Month: //父亲是月
				result[0].segmentCode[i].codes = M_Day_Min - 1;
				result[0].segmentCode[i].params = (base << M_BitMove) | M_Day_Level;
				if(isLeapYear(preData))
					result[1].segmentCode[i].codes = monthsarray[0];
				else
					result[1].segmentCode[i].codes = monthsarray[(int)code->segmentCode[i - 1].codes + 1];
				result[1].segmentCode[i].params = (base << M_BitMove) | M_Day_Level;
				break;
			case (int)UTSCElementType::Day: //父亲是日
				result[0].segmentCode[i].codes = M_Hour_Min;
				result[0].segmentCode[i].params = (base << M_BitMove) | M_Hour_Level;
				result[1].segmentCode[i].codes = M_Hour_Max - 1;
				result[1].segmentCode[i].params = (base << M_BitMove) | M_Hour_Level;
				break;
			case (int)UTSCElementType::Hour: //父亲是小时
				result[0].segmentCode[i].codes = M_Minute_Min;
				result[0].segmentCode[i].params = (base << M_BitMove) | M_Minute_Level;
				result[1].segmentCode[i].codes = M_Minute_Max - 1;
				result[1].segmentCode[i].params = (base << M_BitMove) | M_Minute_Level;
				break;
			case (int)UTSCElementType::Minute: //父亲是分钟
				result[0].segmentCode[i].codes = M_Second_Min;
				result[0].segmentCode[i].params = (base << M_BitMove) | M_Second_Level;
				result[1].segmentCode[i].codes = M_Second_Max - 1;
				result[1].segmentCode[i].params = (base << M_BitMove) | M_Second_Level;
				break;
			case (int)UTSCElementType::Second: //父亲是秒
				result[0].segmentCode[i].codes = M_Milisecond_Min;
				result[0].segmentCode[i].params = (base << M_BitMove) | M_Milisecond_Level;
				result[1].segmentCode[i].codes = M_Milisecond_Max - 1;
				result[1].segmentCode[i].params = (base << M_BitMove) | M_Milisecond_Level;
				break;
			default:
				break;
			}
		}
		size = 2;
	}
	//相邻时间查询
	else
	{
		//Geo类型时间
		if (code->segmentCode[0].params == M_Gyr_parm || code->segmentCode[0].params == M_Myr_parm || code->segmentCode[0].params == M_kyr_parm)
		{
			int i = 0;
			int j = 0;
			std::vector<int> lefttimedata;
			std::vector<int> righttimedata;

			//辅助变量存放所有的时间值
			while (code->segmentCode[i].params != M_unknown_parm && i < code->size)
			{
				lefttimedata.push_back(code->segmentCode[i].codes+1);
				righttimedata.push_back(code->segmentCode[i].codes+1);
				++i;
			}

			//调用函数得到相邻时间
			adjustGeoTime(lefttimedata, -1);
			adjustGeoTime(righttimedata, 1);

			result[0].signal = code->signal;
			result[1].signal = code->signal;

			//将辅助变量中的时间存到编码中
			for (; j < i; j++)
			{
				if(lefttimedata[j] == 0)
				{
					result[0].segmentCode[j].params = M_unknown_parm;
				}
				else
				{
					result[0].segmentCode[j].codes = lefttimedata[j] - 1;
					result[0].segmentCode[j].params = code->segmentCode[j].params;
				}
				if (righttimedata[j] == 0)
				{
					result[1].segmentCode[j].params = M_unknown_parm;
				}
				else
				{
					result[1].segmentCode[j].codes = righttimedata[j] - 1;
					result[1].segmentCode[j].params = code->segmentCode[j].params;
				}
			}
		}
		//UTC类时间
		else
		{
			int i = 0;
			int j = 0;
			while (code->segmentCode[i].params != M_unknown_parm && i < code->size)
			{
				++i;
			}
			//首先将原始编码全部拷贝到左右邻域中
			for (; j < i; j++)
			{
				result[0].segmentCode[j].codes = code->segmentCode[j].codes;
				result[0].segmentCode[j].params = code->segmentCode[j].params;
				result[1].segmentCode[j].codes = code->segmentCode[j].codes;
				result[1].segmentCode[j].params = code->segmentCode[j].params;
			}
			result[0].signal = code->signal;
			result[1].signal = code->signal;
			//将编码中的时间值放入中间变量中存储
			TimeData left_time_data = { 0,0,0,0,0,0,0 };
			TimeData right_time_data = { 0,0,0,0,0,0,0 };
			USTC2TimeData(code, left_time_data);
			USTC2TimeData(code, right_time_data);

			//判断该编码中的最小时间单位
			int type = (int)(code->segmentCode[j - 1].params >> M_BitMove) & 0x0F;

			//得到左右时间值以中间变量的形式存储
			getNeighborTimeData(left_time_data, right_time_data,(UTSCElementType)type);
	
			//重新转回到编码中
			timeData2UTSC(left_time_data, right_time_data, result, code->signal);
		}	
		size = 2;
	}
	return true;
}
 

/// <summary>
/// 时间拓扑关系查询，共三种情况的查询。一共十三种关系
/// 1.时间点与时间点之间的拓扑关系查询：A在B之前Before，A在B之后After，相同Equal
/// 2.时间点与时间片段之间的拓扑关系查询：A在B之前Before，A在B之后After，A与B的起点相同StartWith，A与B的终点相同FinishWith，A在B的中间ContainedBy
/// 3.时间片段与时间片段之间的拓扑关系查询:
/// A在B之前Before，A在B之后After，A和B一起开始（A比B短）StartWith，A和B一起开始（A比B长）StartBy，A和B一起结束（A比B短）FinishWith，A和B一起结束（A比B长）FinishBy
/// A和B相等Equal，A和B相交叉（A比B早），OverlapWith，A和B相交叉（A比B晚）OverlapBy，A包含B Contain，A被B包含ContainedBy，A和B错开（A开始，B结束）MetBy，A和B错开（A结束，B开始）MeetWith
/// </summary>
/// <param name="code1">编码1</param>
/// <param name="code2">编码2</param>
/// <param name="type">查询对象的类型：type=1：时间点与时间点查询；type=2：时间点与时间片段查询；type=3：时间片段与时间片段查询</param>
/// <returns></returns>
NNU::UTSC::UTSCTopoType UTSCImpl::topoQuery(UTSCElementCode* code1, UTSCElementCode* code2,int type)
{
	if (type == 1)
		return topoQueryPointToPoint(code1, code2, 0);
	else if (type == 2)
		return topoQueryPointToInterval(&code1[0], &code2[0], &code2[1]);
	else if (type == 3)
		return topoQueryIntervalToInterval(&code1[0], &code1[1], &code2[0], &code2[1]);
	else
		return UTSCTopoType::Unkonwn;
}



/*************************************private类成员函数实现**************************************************/
/// <summary>
/// 生成编码信息（时间点）
/// </summary>
void UTSCImpl::assignCode(UTSCElementCode*& code, UTSCTime* time, uint8_t tempBase, uint8_t tempLevel, int index)
{
	//当时间类型为年时进行特殊处理（与原点进行判断）
	if (tempBase == static_cast<uint8_t>(UTSCElementType::Year))
	{
		code->segmentCode[index].params = (tempBase << M_BitMove) | tempLevel;
		if (time->segmentTime[index].data >= M_TimeOrigin)
		{
			code->segmentCode[index].codes = (time->segmentTime[index].data - M_TimeOrigin);
			code->signal = 1;
		}
		else if (time->segmentTime[index].data < M_TimeOrigin)
		{
			code->segmentCode[index].codes = (M_TimeOrigin - time->segmentTime[index].data);
			code->signal = 0;
		}
	}

	//赋值操作，取tempbase前四位与templevel组成parm
	else
	{
		code->segmentCode[index].codes = (time->segmentTime[index].data);
		code->segmentCode[index].params = (tempBase << M_BitMove) | tempLevel;
	}
}


/// <summary>
/// 生成解码信息（时间点）
/// </summary>
void UTSCImpl::assignTimeInfo(UTSCTime*& time, int signal, uint16_t data, unsigned char base, int index)
{
	if ((UTSCElementType)base == UTSCElementType::Year)
	{
		time->segmentTime[index].elementType = (UTSCElementType)base;
		if (signal == 1)
			time->segmentTime[index].data = data + M_TimeOrigin;
		else
			time->segmentTime[index].data = M_TimeOrigin - data;
	}

	//赋值操作
	else
	{
		time->segmentTime[index].data = data;
		time->segmentTime[index].elementType = (UTSCElementType)base;
	}
}



/*时间范围私有函数*/
// 根域 [0..(2^L-1)] 上用 dyadic 节点覆盖 [qlo..qhi]（闭区间）
void UTSCImpl::coverDyadicRange(int L, int qlo, int qhi, std::vector<DyadicNode>& out) {
	if (qlo > qhi) return;
	const int DOMAIN_MAX = (1 << L) - 1;
	int lo = std::max(0, qlo);
	int hi = std::min(DOMAIN_MAX, qhi);
	if (lo > hi) return;

	std::function<void(int, int, uint8_t, uint16_t)> dfs = [&](int ns, int ne, uint8_t depth, uint16_t path) {
		if (hi < ns || lo > ne) return;
		if (lo <= ns && ne <= hi) {
			out.push_back({ depth, path, ns, ne });
			return;
		}
		if (depth == L) {
			out.push_back({ depth, path, ns, ne });
			return;
		}
		int mid = (ns + ne) >> 1;
		dfs(ns, mid, (uint8_t)(depth + 1), (uint16_t)(path << 1));
		dfs(mid + 1, ne, (uint8_t)(depth + 1), (uint16_t)((path << 1) | 1));
		};
	dfs(0, DOMAIN_MAX, 0, 0);
}

// 反向：给定 (L, depth, path) 求该节点在 [0..2^L-1] 上的覆盖区间
void UTSCImpl::getNodeRange(int L, uint8_t depth, uint16_t path, int& outLo, int& outHi) {
	int ns = 0, ne = (1 << L) - 1;
	for (int d = 0; d < depth; ++d) {
		int mid = (ns + ne) >> 1;
		int bit = (path >> (depth - 1 - d)) & 1;
		if (bit == 0) ne = mid;
		else          ns = mid + 1;
	}
	outLo = ns; outHi = ne;
}

// 系统→单位顺序
void UTSCImpl::getUnitOrder(UTSCTimeSystemType sys, std::vector<UTSCElementType>& order) {
	order.clear();
	if (sys == UTSCTimeSystemType::UTC) {
		order = {
			UTSCElementType::Year,
			UTSCElementType::Month,
			UTSCElementType::Day,
			UTSCElementType::Hour,
			UTSCElementType::Minute,
			UTSCElementType::Second,
			UTSCElementType::Millisecond
		};
	}
	else {
		// 地质时间（从大到小）
		order = {
			UTSCElementType::GigaYear,
			UTSCElementType::MegaYear,
			UTSCElementType::KiloYear,
			UTSCElementType::Year
		};
	}
}

// 常量最小值
static int unitMinConst(UTSCElementType t) {
	switch (t) {
	case UTSCElementType::Month:       return M_Month_Min;
	case UTSCElementType::Day:         return M_Day_Min;
	case UTSCElementType::Hour:        return M_Hour_Min;
	case UTSCElementType::Minute:      return M_Minute_Min;
	case UTSCElementType::Second:      return M_Second_Min;
	case UTSCElementType::Millisecond: return M_Milisecond_Min;
	case UTSCElementType::GigaYear:    return M_GeoTime_Min;
	case UTSCElementType::MegaYear:    return M_GeoTime_Min;
	case UTSCElementType::KiloYear:    return M_GeoTime_Min;
	case UTSCElementType::Year:        return 0; // UTC 年：这里不用；地质年：又属于 GeoTime（见下面 unitMaxConst）
	default: return 0;
	}
}

// 常量最大值（不含 Day 的动态）
static int unitMaxConst(UTSCElementType t) {
	switch (t) {
	case UTSCElementType::Month:       return M_Month_Max;
	case UTSCElementType::Hour:        return M_Hour_Max - 1;        // 0..23
	case UTSCElementType::Minute:      return M_Minute_Max - 1;      // 0..59
	case UTSCElementType::Second:      return M_Second_Max - 1;      // 0..59
	case UTSCElementType::Millisecond: return M_Milisecond_Max - 1;  // 0..999
	case UTSCElementType::GigaYear:    return M_GeoTime_Max - 1;
	case UTSCElementType::MegaYear:    return M_GeoTime_Max - 1;
	case UTSCElementType::KiloYear:    return M_GeoTime_Max - 1;
	case UTSCElementType::Year:        return M_GeoTime_Max - 1; // 不直接用；UTC 年由 signal+offset 处理
	case UTSCElementType::Day:         return 31;      // 仅兜底，真正值由 daysInMonth 决定
	default: return 0;
	}
}

// UTSCImpl 成员：在给定前缀下的最大值（Day 需要 year/month）
int UTSCImpl::unitMaxWithPrefix(UTSCTimeSystemType sys,
	const std::vector<UTSCElementType>& order,
	const std::vector<int>& prefixVals,
	int idx) {
	UTSCElementType t = order[idx];
	if (sys == UTSCTimeSystemType::UTC && t == UTSCElementType::Day) {
		// 从前缀找 Year / Month
		int y = M_TimeOrigin, m = 1;
		for (int k = 0; k < idx; ++k) {
			if (order[k] == UTSCElementType::Year)  y = prefixVals[k];
			if (order[k] == UTSCElementType::Month) m = prefixVals[k];
		}
		return this->daysInMonth(y, m);
	}
	return unitMaxConst(t);
}

int UTSCImpl::unitMin(UTSCElementType t) {
	if (t == UTSCElementType::Year) return 0; // UTC 年（不用于范围直接 min）
	return unitMinConst(t);
}

// 绝对 UTC 年 → 编码 codes/signal
void UTSCImpl::encodeUTCYearPoint(int year, uint16_t& codes, int8_t& signal) {
	if (year >= M_TimeOrigin) { // 1950之后
		codes = static_cast<uint16_t>(year - M_TimeOrigin);
		signal = 1;
	}
	else{
		codes = static_cast<uint16_t>(M_TimeOrigin - year);
		signal = 0;
	}
}
int UTSCImpl::decodeUTCYearPoint(uint16_t codes, int8_t signal) {
	if (signal == 1) {
		if (codes != M_TimeOrigin) return M_TimeOrigin + codes;
		return M_TimeOrigin;
	}
	else { 
		return M_TimeOrigin - codes;
	}
}

// 写一个“点”到 enc.segmentCode[idx]（level=该单位最大层）
//  - Year(UTC) 用 signal/codes 表达；其他单位直接 codes = 值
void UTSCImpl::putPoint(UTSCElementCode& enc, int idx, UTSCElementType t, int value) {
	const uint8_t base = static_cast<uint8_t>(t);
	const uint8_t Lmax = UTSCElementTypeMap[t]; // 该单位允许的最大层（4bit）
	enc.segmentCode[idx].params = static_cast<uint8_t>((base << M_BitMove) | Lmax);

	if (t == UTSCElementType::Year) {
		// 这里 Year 的 codes/signal 在外面单独处理（UTC）或直接赋值（Geo）
		// 保持 params，codes 在外面写
		enc.segmentCode[idx].codes = static_cast<uint16_t>(value);
	}
	else {
		enc.segmentCode[idx].codes = static_cast<uint16_t>(value);
	}
}

// Year(UTC) 点写入（会填写 signal/codes）
void UTSCImpl::putYearPointUTC(UTSCElementCode& enc, int idx, int absYear) {
	const uint8_t base = static_cast<uint8_t>(UTSCElementType::Year);
	const uint8_t Lmax = UTSCElementTypeMap[UTSCElementType::Year];
	enc.segmentCode[idx].params = static_cast<uint8_t>((base << M_BitMove) | Lmax);
	uint16_t codeV = 0; int8_t sig = 1;
	encodeUTCYearPoint(absYear, codeV, sig);
	enc.segmentCode[idx].codes = codeV;
	enc.signal = sig;
}

// 写“节点”（level = 实际 depth，codes = path）
void UTSCImpl::putNode(UTSCElementCode& enc, int idx, UTSCElementType t, uint8_t depth, uint16_t path) {
	const uint8_t base = static_cast<uint8_t>(t);
	enc.segmentCode[idx].params = static_cast<uint8_t>((base << M_BitMove) | (depth & 0x0F));
	enc.segmentCode[idx].codes = path;
}

// 初始化一个空编码帧
void UTSCImpl::initCodeFrame(UTSCElementCode& enc) {
	// 如果没有这个宏，可用 0 代表“无效”
	for (int i = 0; i < enc.size; ++i) {
		enc.segmentCode[i].params = 0; // M_unknown_parm
		enc.segmentCode[i].codes = 0;
	}
	enc.signal = 0;
}

// 从单个编码中识别“最后一个被设置的片段”的索引
int UTSCImpl::lastSetIndex(const UTSCElementCode& enc) {
	int last = -1;
	for (int i = 0; i < enc.size; ++i) {
		if (enc.segmentCode[i].params != 0) last = i;
	}
	return last;
}

// 规范化：把 start / end 的“维度长度”补齐为与系统相符（不足的设 Unknown）
// 同时输出按系统顺序排列的 order
void UTSCImpl::normalizeToOrder(UTSCTime* t,
	const std::vector<UTSCElementType>& order,
	std::vector<int>& vals,
	std::vector<bool>& hasVal) {
	vals.assign(order.size(), 0);
	hasVal.assign(order.size(), false);
	// 假设输入的 segment 顺序与你既有相同（Year, Month, ...）
	for (size_t i = 0; i < order.size() && i < (size_t)t->size; ++i) {
		if (t->segmentTime[i].elementType == order[i]) {
			vals[i] = t->segmentTime[i].data;
			hasVal[i] = (t->segmentTime[i].elementType != UTSCElementType::Unknown);
		}
	}
}

// 把“下界（start）补齐为最小”，把“上界（end）补齐为最大”以对齐精度
void UTSCImpl::fillLowHigh(UTSCTimeSystemType sys,
	const std::vector<UTSCElementType>& order,
	std::vector<int>& sv, std::vector<bool>& sHave,
	std::vector<int>& ev, std::vector<bool>& eHave) {
	// 找两者最后一个“有值”的索引
	int sLast = -1, eLast = -1;
	for (int i = 0; i < (int)order.size(); ++i) {
		if (sHave[i]) sLast = i;
		if (eHave[i]) eLast = i;
	}
	int target = std::max(sLast, eLast);
	if (target < 0) return;

	// 用“最小/最大”把缺省补齐到 target
	for (int i = 0; i <= target; ++i) {
		if (!sHave[i]) {
			// start 缺 → 填最小
			if (order[i] == UTSCElementType::Day && sys == UTSCTimeSystemType::UTC) {
				// 需要 Year/Month 前缀
				int y = sv[0], m = (i >= 1 ? sv[1] : 1);
				sv[i] = std::max(1, std::min(this->daysInMonth(y, m), this->daysInMonth(y, m))); // ==1
			}
			else {
				sv[i] = unitMin(order[i]);
			}
			sHave[i] = true;
		}
		if (!eHave[i]) {
			// end 缺 → 填最大
			if (order[i] == UTSCElementType::Day && sys == UTSCTimeSystemType::UTC) {
				int y = ev[0], m = (i >= 1 ? ev[1] : 1);
				ev[i] = this->daysInMonth(y, m);
			}
			else {
				ev[i] = unitMaxConst(order[i]);
			}
			eHave[i] = true;
		}
	}
}

/// <summary>
/// 在“前缀固定到 idx-1”的前提下，尝试用某一单位 idx 的 dyadic 节点覆盖 [lo..hi]
/// </summary>
/// <param name="sys">时间系统类型（UTC 或 Geo）</param>
/// <param name="order">时间单位顺序</param>
/// <param name="prefix">前缀数值，如已确定的 Year/Month/Day</param>
/// <param name="idxUnit">当前正在处理的单位索引</param>
/// <param name="lo">当前单位的值范围</param>
/// <param name="hi">当前单位的值范围</param>
/// <param name="out">输出编码数组</param>
void UTSCImpl::emitUnitRange(UTSCTimeSystemType sys,
    const std::vector<UTSCElementType>& order,
    const std::vector<int>& prefix, int idxUnit,
    int lo, int hi,
    std::vector<UTSCElementCode>& out)
{
    UTSCElementType unit = order[idxUnit];
    int L = UTSCElementTypeMap.at(unit);	// 当前单位对应的编码长度
    if (L <= 0) return;

    // clamp 到该单位真实取值域
    int uMin = unitMin(unit);
    int uMax = unitMaxWithPrefix(sys, order, prefix, idxUnit);
    lo = std::max(lo, uMin);
    hi = std::min(hi, uMax);
    if (lo > hi) return;

    // Helper: 在 out 中原位构造一个编码并返回引用
    auto makeEncInOut = [&]() -> UTSCElementCode& {
        out.emplace_back(M_Type_number);
        UTSCElementCode &enc = out.back();
        initCodeFrame(enc);		// 初始化 segmentCode 内存和 size
        return enc;
    };

    // 写前缀
    auto writePrefixToEnc = [&](UTSCElementCode &enc) {
        for (int j = 0; j < idxUnit; ++j) {
            UTSCElementType tj = order[j];
            if (tj == UTSCElementType::Year && sys == UTSCTimeSystemType::UTC) {
                putYearPointUTC(enc, j, prefix[j]);   // 年份编码
            } else {
                putPoint(enc, j, tj, prefix[j]);	// 普通单位编码
                if (tj == UTSCElementType::Year && sys == UTSCTimeSystemType::Geo) {
                    enc.signal = 0; // 地质年不需要 signal
                }
            }
        }
    };

    // 写当前单位节点编码
    auto pushWithPrefixAndNode = [&](int depth, uint16_t path, int8_t yearSignal = 0) {
        UTSCElementCode &enc = makeEncInOut();
        writePrefixToEnc(enc);		// 写前缀
        putNode(enc, idxUnit, unit, static_cast<uint8_t>(depth), path);	// 写 dyadic 节点
        if (order[idxUnit] == UTSCElementType::Year && sys == UTSCTimeSystemType::UTC) {
            enc.signal = yearSignal;	 // 仅 Year UTC 写 signal
        }
    };

    // Year(UTC) 的坐标映射
    auto yearCoordNeg = [&](int yr) -> int {
        return (M_TimeOrigin) - yr;
    };
    auto yearCoordPos = [&](int yr) -> int {
        return (yr - (M_TimeOrigin));
    };

    // 特殊处理 UTC Year
    if (sys == UTSCTimeSystemType::UTC && unit == UTSCElementType::Year) {
        // 左半
        if (lo <= M_TimeOrigin - 1) {
            int A = std::max(lo, M_TimeOrigin - 10000000);
            int B = std::min(hi, M_TimeOrigin - 1);
            if (A <= B) {
                std::vector<DyadicNode> nodes;
                coverDyadicRange(L, yearCoordNeg(B), yearCoordNeg(A), nodes);
                for (auto &n : nodes) {
                    pushWithPrefixAndNode(n.depth, n.path, 0);
                }
            }
        }
        // origin 年（1950）
        if (lo <= M_TimeOrigin && M_TimeOrigin <= hi) {
            UTSCElementCode &enc = makeEncInOut();
            putYearPointUTC(enc, idxUnit, M_TimeOrigin);
        }
        // 右半
        if (hi >= M_TimeOrigin) {
            int A = std::max(lo, M_TimeOrigin);
            int B = hi;
            if (A <= B) {
                std::vector<DyadicNode> nodes;
                coverDyadicRange(L, yearCoordPos(A), yearCoordPos(B), nodes);
                for (auto &n : nodes) {
                    pushWithPrefixAndNode(n.depth, n.path, 1);
                }
            }
        }
        return;
    }

    // 其它单位
    std::vector<DyadicNode> nodes;
    coverDyadicRange(L, lo, hi, nodes);
    for (auto &n : nodes) {
        pushWithPrefixAndNode(n.depth, n.path, 0);
    }
}


// 私有：尝试用一个 dyadic 节点表示整个最高精度区间（如果可能）
// 返回 true 时：已把唯一编码 push 到 out 中；返回 false 则没有任何输出。
bool UTSCImpl::trySingleNodeEncode(UTSCTimeSystemType sys,
	const std::vector<UTSCElementType>& cutOrder,
	const std::vector<int>& sv, const std::vector<int>& ev,
	std::vector<UTSCElementCode>& out)
{
	if (cutOrder.empty()) return false;
	int idx = (int)cutOrder.size() - 1;             // 最高精度所在索引（cutOrder 最后一个）
	UTSCElementType unit = cutOrder[idx];
	int L = UTSCElementTypeMap.at(unit);
	if (L <= 0) return false;

	// 1) 只有当除最高精度以外的所有前缀都相等时，才有可能一次性命中
	for (int i = 0; i < idx; ++i) {
		if (sv[i] != ev[i]) return false;
	}

	// 2) 取最高精度的数值区间
	int lo = sv[idx];
	int hi = ev[idx];

	// 3) 针对 Year(UTC) 需要按两侧映射到 dyadic 空间；其他单位直接使用 lo..hi
	std::vector<DyadicNode> nodes;
	if (sys == UTSCTimeSystemType::UTC && unit == UTSCElementType::Year) {
		// 左侧 ( < origin )
		if (hi <= M_TimeOrigin - 1) {
			auto yearCoordNeg = [&](int yr)->int { return (M_TimeOrigin - 1) - yr; };
			coverDyadicRange(L, yearCoordNeg(hi), yearCoordNeg(lo), nodes);
		}
		// 右侧 ( > origin )
		else if (lo >= M_TimeOrigin + 1) {
			auto yearCoordPos = [&](int yr)->int { return (yr - (M_TimeOrigin + 1)); };
			coverDyadicRange(L, yearCoordPos(lo), yearCoordPos(hi), nodes);
		}
		// 跨越 origin（例如 lo < 1950 < hi） —— 不能由单个节点表示
		else {
			return false;
		}
	}
	else {
		// 普通单位直接映射到 root 域（0..2^L-1）
		coverDyadicRange(L, lo, hi, nodes);
	}

	// 4) 如果 dyadic 覆盖结果只有 1 个节点，则这个节点即为单节点覆盖，可直接生成编码并返回
	if (nodes.size() == 1) {
		DyadicNode n = nodes[0];

		// 在 out 中原位构造一个编码（避免拷贝问题）
		out.emplace_back(M_Type_number);
		UTSCElementCode& enc = out.back();
		initCodeFrame(enc);

		// 写前缀点（0..idx-1）
		for (int j = 0; j < idx; ++j) {
			UTSCElementType tj = cutOrder[j];
			if (tj == UTSCElementType::Year && sys == UTSCTimeSystemType::UTC) {
				putYearPointUTC(enc, j, sv[j]); // 前缀值相同：sv[j] == ev[j]
			}
			else {
				putPoint(enc, j, tj, sv[j]);
			}
		}

		// 写当前单位的节点（depth/path）
		putNode(enc, idx, unit, n.depth, n.path);

		// 不在这里设置 signal（我们统一在 encode 最后设置序列第0位的 signal）
		return true;
	}

	return false;
}



/// <summary>
/// 解码
/// </summary>
/// <param name="code"></param>
/// <param name="minIf"></param>
/// <param name="outTime"></param>
/// <returns></returns>
bool UTSCImpl::decodeSingleMinMax(const UTSCElementCode& code,
	bool minIf,
	UTSCTime*& outTime) {
	if (!outTime) outTime = new UTSCTime(M_Type_number);

	// 判定时间体系（保留你原来的判定规则）
	if (code.segmentCode[0].params == M_Gyr_parm ||
		code.segmentCode[0].params == M_Myr_parm ||
		code.segmentCode[0].params == M_kyr_parm)
		outTime->system = UTSCTimeSystemType::Geo;
	else
		outTime->system = UTSCTimeSystemType::UTC;

	// 单位顺序
	std::vector<UTSCElementType> order; getUnitOrder(outTime->system, order);
	int totalLevels = (int)order.size();

	int last = lastSetIndex(code);
	if (last < 0) return false;

	// 我们**只填充到 code 的最后一层**（不填充更细单位）
	outTime->size = last + 1;

	// 把前面的维度（0..last-1）按“点”的方式写入（这些在 encode 中是具体值）
	for (int i = 0; i < last; ++i) {
		uint8_t params = code.segmentCode[i].params;
		if (params == 0) return false; // 不应出现
		UTSCElementType base = (UTSCElementType)((params >> M_BitMove) & 0x0F);
		outTime->segmentTime[i].elementType = base;
		if (base == UTSCElementType::Year && outTime->system == UTSCTimeSystemType::UTC) {
			outTime->segmentTime[i].data = decodeUTCYearPoint(code.segmentCode[i].codes, code.signal);
		}
		else {
			outTime->segmentTime[i].data = (int)code.segmentCode[i].codes;
		}
	}

	// 处理最后一层（index = last）
	{
		uint8_t params = code.segmentCode[last].params;
		if (params == 0) return false;
		UTSCElementType base = (UTSCElementType)((params >> M_BitMove) & 0x0F);
		uint8_t level = params & 0x0F;
		uint16_t path = code.segmentCode[last].codes;
		outTime->segmentTime[last].elementType = base;

		int Lmax = UTSCElementTypeMap[base];
		if (level == Lmax) {
			// 叶：具体时间点（仍然只写到最后这一层）
			if (base == UTSCElementType::Year && outTime->system == UTSCTimeSystemType::UTC) {
				outTime->segmentTime[last].data = decodeUTCYearPoint(code.segmentCode[last].codes, code.signal);
			}
			else {
				outTime->segmentTime[last].data = (int)path;
			}
		}
		else {
			// 节点：代表 base 层的一个区间（取 lo / hi）
			int lo = 0, hi = 0;
			getNodeRange(Lmax, level, path, lo, hi);

			// 如果是 Day 层并且前缀包含 Year/Month，则 clamp 到真实天数
			if (base == UTSCElementType::Day && outTime->system == UTSCTimeSystemType::UTC) {
				int y = -1, m = -1;
				// 在 outTime 已填的前缀中查找 Year/Month
				for (int t = 0; t <= last; ++t) {
					if (outTime->segmentTime[t].elementType == UTSCElementType::Year) {
						y = outTime->segmentTime[t].data;
					}
					else if (outTime->segmentTime[t].elementType == UTSCElementType::Month) {
						m = outTime->segmentTime[t].data;
					}
				}
				if (y > 0 && m > 0) {
					int md = this->daysInMonth(y, m);
					lo = std::max(lo, 1);
					hi = std::min(hi, md);
				}
				// 若没有 year/month 前缀，则无法 clamp，保留 lo/hi 原样
			}

			outTime->segmentTime[last].data = (minIf ? lo : hi);
		}
	}

	// **关键**：不自动填充 last 之后的更低精度（不设置 minutes/seconds/milliseconds）
	// outTime->size 已经设为 last+1，调用者据此知道精度边界

	return true;
}



// 比较两个等长的向量 a, b
// return -1: a < b, 0: a == b, 1: a > b
int UTSCImpl::compareTuple(const std::vector<int>& a, const std::vector<int>& b) {
	int n = std::min(a.size(), b.size());
	for (int i = 0; i < n; i++) {
		if (a[i] < b[i]) return -1;
		if (a[i] > b[i]) return 1;
	}
	if (a.size() < b.size()) return -1;
	if (a.size() > b.size()) return 1;
	return 0;
}

// sys: 时间系统
// cutOrder: 当前维度顺序
// cur: 当前起点
// ev: 结束点
// return: 可以覆盖的最大维度索引 k
int UTSCImpl::findLargestDyadic(UTSCTimeSystemType sys,
	const std::vector<UTSCElementType>& cutOrder,
	const std::vector<int>& cur,
	const std::vector<int>& ev) {
	int n = cutOrder.size();
	// 从最高精度往下找
	for (int k = n - 1; k >= 0; k--) {
		int lo = cur[k];
		int maxv = unitMaxWithPrefix(sys, cutOrder, cur, k);
		// 这里的“最大 dyadic 区间”是：从 lo 开始，长度必须是 2^m，对齐到 2^m 边界
		int len = 1;
		while (true) {
			int blockStart = (lo / len) * len;
			int blockEnd = blockStart + len - 1;
			if (blockStart != lo) break; // 必须对齐
			if (blockEnd > maxv) break;  // 超出单位最大值
			if (blockEnd > ev[k]) break; // 超出剩余区间
			len <<= 1;
		}
		len >>= 1;
		if (len > 0) {
			return k;
		}
	}
	return n - 1; // 默认用最后一维
}

void UTSCImpl::tailFillToMin(const std::vector<UTSCElementType>& order,
	std::vector<int>& v, int fromIdx) {
	for (int j = fromIdx; j < (int)order.size(); ++j) v[j] = unitMin(order[j]);
}

void UTSCImpl::copyPrefix(const std::vector<int>& src, std::vector<int>& dst, int upto) {
	for (int i = 0; i <= upto; ++i) dst[i] = src[i];
}

// helper: 截断到指定层级
static void truncateBelow(std::vector<int>& v, int keepIdx) {
	v.resize(keepIdx + 1); // 只保留到 keepIdx 层
}

void UTSCImpl::makeVirtualRanges(UTSCTimeSystemType sys,
	const std::vector<UTSCElementType>& cutOrder,
	const std::vector<int>& sv,
	const std::vector<int>& ev,
	std::vector<std::pair<std::vector<int>, std::vector<int>>>& outRanges)
{
	outRanges.clear();
	const int last = (int)cutOrder.size() - 1;

	int splitIdx = -1;
	for (int i = 0; i < last; ++i) {
		if (sv[i] != ev[i]) { splitIdx = i; break; }
	}
	if (splitIdx < 0) {
		outRanges.emplace_back(sv, ev);
		return;
	}

	// (1-1) 头：保持完整精度
	{
		std::vector<int> lo = sv;
		std::vector<int> hi = sv;
		hi[last] = unitMaxWithPrefix(sys, cutOrder, hi, last);
		if (compareTuple(lo, hi) <= 0) outRanges.emplace_back(std::move(lo), std::move(hi));
	}

	// (2) 自上而下
	for (int p = last - 1; p > splitIdx; --p) {
		// (2-1) 开始侧
		{
			std::vector<int> lo = sv, hi = sv;
			lo[p] = sv[p] + 1;
			hi[p] = unitMaxWithPrefix(sys, cutOrder, hi, p);

			// ⬇ 截断到 p 层级
			truncateBelow(lo, p);
			truncateBelow(hi, p);

			if (compareTuple(lo, hi) <= 0)
				outRanges.emplace_back(std::move(lo), std::move(hi));
		}

		// (2-2) 结束侧
		{
			std::vector<int> lo = ev, hi = ev;
			lo[p] = unitMin(cutOrder[p]);
			hi[p] = ev[p] - 1;

			// ⬇ 截断到 p 层级
			truncateBelow(lo, p);
			truncateBelow(hi, p);

			if (compareTuple(lo, hi) <= 0)
				outRanges.emplace_back(std::move(lo), std::move(hi));
		}
	}

	// (4) 最低不一致尺度
	{
		std::vector<int> lo = sv, hi = ev;
		lo[splitIdx] = sv[splitIdx] + 1;
		hi[splitIdx] = ev[splitIdx] - 1;

		// ⬇ 截断到 splitIdx 层级
		truncateBelow(lo, splitIdx);
		truncateBelow(hi, splitIdx);

		if (compareTuple(lo, hi) <= 0)
			outRanges.emplace_back(std::move(lo), std::move(hi));
	}

	// (1-2) 尾：保持完整精度
	{
		std::vector<int> lo = ev, hi = ev;
		lo[last] = unitMin(cutOrder[last]);
		if (compareTuple(lo, hi) <= 0)
			outRanges.emplace_back(std::move(lo), std::move(hi));
	}
}


/// <summary>
/// 时间点与时间点之间的拓扑关系查询：A在B之前Before，A在B之后After，相同Equal
/// </summary>
/// <param name="srcCode"></param>
/// <param name="tagCode"></param>
/// <param name="iterate"></param>
/// <returns></returns>
NNU::UTSC::UTSCTopoType UTSCImpl::topoQueryPointToPoint(NNU::UTSC::UTSCElementCode *srcCode, NNU::UTSC::UTSCElementCode *tagCode,int iterate)
{
	//逐单位比较各时间的大小
	while (srcCode->segmentCode[iterate].params != M_unknown_parm && iterate < srcCode->size && tagCode->segmentCode[iterate].params != M_unknown_parm && iterate < tagCode->size)
	{
		//取出src的base和code码
		uint8_t src_base = (srcCode->segmentCode[iterate].params >> M_BitMove) & 0x0F;
		uint16_t src_code = srcCode->segmentCode[iterate].codes;
												
		//取出tag的base和code码					 
		uint8_t tag_base = (tagCode->segmentCode[iterate].params >> M_BitMove) & 0x0F;
		uint16_t tag_code = tagCode->segmentCode[iterate].codes;

		//依据base（时间单位）比较
		if (src_base < tag_base)
			return UTSCTopoType::Before;
		else if (src_base > tag_base)
			return UTSCTopoType::After;
		//当时间单位相同时再比较时间大小
		else
		{
			if (src_code > tag_code)
				return UTSCTopoType::After;
			else if (src_code < tag_code)
				return UTSCTopoType::Before;
			//当时间大小相同时再递归比较后一位时间大小
			else
				return topoQueryPointToPoint(srcCode, tagCode, iterate + 1);
		}
	}
	//当上述情况都满足时，一个时间点比另一个时间点更精确时的情况
	if (srcCode->segmentCode[iterate].params != M_unknown_parm)
		return  UTSCTopoType::After;
	else if (tagCode->segmentCode[iterate].params != M_unknown_parm)
		return UTSCTopoType::Before;
	else
		return UTSCTopoType::Equal;

	return UTSCTopoType::Unkonwn;
}

/// <summary>
///  时间点与时间片段之间的拓扑关系查询：A在B之前Before，A在B之后After，A与B的起点相同StartWith，A与B的终点相同FinishWith，A在B的中间ContainedBy
/// </summary>
/// <param name="srcCode"></param>
/// <param name="tagCodeStart"></param>
/// <param name="tagCodeEnd"></param>
/// <returns></returns>
NNU::UTSC::UTSCTopoType UTSCImpl::topoQueryPointToInterval(NNU::UTSC::UTSCElementCode* srcCode, NNU::UTSC::UTSCElementCode* tagCodeStart, NNU::UTSC::UTSCElementCode* tagCodeEnd)
{
	//时间片段由两个时间点组成，判断时间点和时间片段的关系，即用一个时间点与另外两个时间点进行时间点与时间点的比较
	if (topoQueryPointToPoint(srcCode, tagCodeStart, 0) == UTSCTopoType::Before)
		return UTSCTopoType::Before;
	else if (topoQueryPointToPoint(srcCode, tagCodeEnd, 0) == UTSCTopoType::After)
		return UTSCTopoType::After;
	else if (topoQueryPointToPoint(srcCode, tagCodeStart, 0) == UTSCTopoType::Equal)
		return  UTSCTopoType::StartWith;
	else if (topoQueryPointToPoint(srcCode, tagCodeEnd, 0) == UTSCTopoType::Equal)
		return  UTSCTopoType::FinishWith;
	else 
		return  UTSCTopoType::ContainedBy;
}

/// <summary>
/// 时间片段与时间片段之间的拓扑关系查询：
/// A在B之前Before，A在B之后After，A和B一起开始（A比B短）StartWith，A和B一起开始（A比B长）StartBy，A和B一起结束（A比B短）FinishWith，A和B一起结束（A比B长）FinishBy
/// A和B相等Equal，A和B相交叉（A比B早），OverlapWith，A和B相交叉（A比B晚）OverlapBy，A包含B Contain，A被B包含ContainedBy，A和B错开（A开始，B结束）MetBy，A和B错开（A结束，B开始）MeetWith
/// <param name="srcCodeEnd"></param>
/// <param name="tagCodeStart"></param>
/// <param name="tagCodeEnd"></param>
/// <returns></returns>
NNU::UTSC::UTSCTopoType UTSCImpl::topoQueryIntervalToInterval(NNU::UTSC::UTSCElementCode* srcCodeStart, NNU::UTSC::UTSCElementCode* srcCodeEnd, NNU::UTSC::UTSCElementCode* tagCodeStart, NNU::UTSC::UTSCElementCode* tagCodeEnd)
{
	if (topoQueryPointToPoint(srcCodeEnd, tagCodeStart, 0) == UTSCTopoType::Before)
		return UTSCTopoType::Before;
	else if (topoQueryPointToPoint(srcCodeStart, tagCodeEnd, 0) == UTSCTopoType::After)
		return UTSCTopoType::After;
	else if (topoQueryPointToPoint(srcCodeStart, tagCodeStart, 0) == UTSCTopoType::Equal)
	{
		if (topoQueryPointToPoint(srcCodeEnd, tagCodeEnd, 0) == UTSCTopoType::Before)
			return UTSCTopoType::StartWith;
		else if (topoQueryPointToPoint(srcCodeEnd, tagCodeEnd, 0) == UTSCTopoType::After)
			return UTSCTopoType::StartBy;
		else
			return UTSCTopoType::Equal;
	}
	else if (topoQueryPointToPoint(srcCodeStart, tagCodeStart, 0) == UTSCTopoType::Before)
	{
		if (topoQueryPointToPoint(srcCodeEnd, tagCodeStart, 0) == UTSCTopoType::Before)
			return UTSCTopoType::Before;
		else if(topoQueryPointToPoint(srcCodeEnd, tagCodeStart, 0) == UTSCTopoType::Equal)
			return  UTSCTopoType::MeetWith;
		else
		{
			if(topoQueryPointToPoint(srcCodeEnd, tagCodeEnd, 0) == UTSCTopoType::Before)
				return UTSCTopoType::OverlapWith;
			else if(topoQueryPointToPoint(srcCodeEnd, tagCodeEnd, 0) == UTSCTopoType::Equal)
				return UTSCTopoType::FinishBy;
			else
				return UTSCTopoType::Contain;
		}
	}
	else if (topoQueryPointToPoint(srcCodeStart, tagCodeStart, 0) == UTSCTopoType::After)
	{
		if(topoQueryPointToPoint(srcCodeEnd, tagCodeEnd, 0) == UTSCTopoType::Before)
			return UTSCTopoType::ContainedBy;
		else if(topoQueryPointToPoint(srcCodeEnd, tagCodeEnd, 0) == UTSCTopoType::Equal)
			return UTSCTopoType::FinishWith;
		else
			return UTSCTopoType::OverlapBy;
	}
	else if(topoQueryPointToPoint(srcCodeStart, tagCodeEnd, 0) == UTSCTopoType::Equal)
		return UTSCTopoType::MetBy;
	else
		return UTSCTopoType::Unkonwn;
}


//检查是否为闰年
bool UTSCImpl::isLeapYear(int year)
{
	return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

//获取某个月的天数
int UTSCImpl::daysInMonth(int year, int month)
{
	switch (month) {
	case 1: case 3: case 5: case 7: case 8: case 10: case 12:
		return M_Big_Month_Days;
	case 4: case 6: case 9: case 11:
		return M_Small_Month_Days;
	case 2:
		return isLeapYear(year) ? M_Feb_LeapYear_Days : M_Feb_NormalYear_Days;
	default:
		return 0;
	}
}

//USTC时间中的值转为TimeData结构
void UTSCImpl::USTC2TimeData(UTSCElementCode* code, TimeData& time)
{
	int i = 0;
	while (code->segmentCode[i].params != M_unknown_parm && i < code->size)
	{
		uint8_t temp_base = (code->segmentCode[i].params >> M_BitMove) & 0x0F;
		uint16_t temp_code = code->segmentCode[i].codes;
		switch ((UTSCElementType)temp_base)
		{
		case UTSCElementType::Year:
			if (code->signal == 1)
			{
				time.year = temp_code + 1 + M_TimeOrigin;
				break;
			}
			else
			{
				time.year = M_TimeOrigin - temp_code - 1;
				break;
			}
		case UTSCElementType::Month:
			time.month = temp_code + 1;
			break;
		case UTSCElementType::Day:
			time.day = temp_code + 1;
			break;
		case UTSCElementType::Hour:
			time.hour = temp_code;
			break;
		case UTSCElementType::Minute:
			time.minute = temp_code;
			break;
		case UTSCElementType::Second:
			time.second = temp_code;
			break;
		case UTSCElementType::Millisecond:
			time.millisecond = temp_code;
			break;
		default:
			break;
		}
		++i;
	}
}

//得到TimeData时间点的左或右时间点
void UTSCImpl::getSingleNeighborTimeData(TimeData& left, UTSCElementType type, int i)
{
	// 处理毫秒
	if (type == UTSCElementType::Millisecond)
		left.millisecond += i;

	if (left.millisecond >= M_Milisecond_Max) {
		left.second += left.millisecond / M_Milisecond_Max;
		left.millisecond %= M_Milisecond_Max;
	}
	else if (left.millisecond < 0) {
		left.second += (left.millisecond - M_Milisecond_Max - 1) / M_Milisecond_Max;
		left.millisecond = (left.millisecond % M_Milisecond_Max + M_Milisecond_Max) % M_Milisecond_Max;
	}

	// 处理秒
	if (type == UTSCElementType::Second)
		left.second += i;
	if (left.second >= M_Second_Max) {
		left.minute += left.second / M_Second_Max;
		left.second %= M_Second_Max;
	}
	else if (left.second < 0) {
		left.minute += (left.second - M_Second_Max - 1) / M_Second_Max;
		left.second = (left.second % M_Second_Max + M_Second_Max) % M_Second_Max;
	}

	// 处理分钟
	if (type == UTSCElementType::Minute)
		left.minute += i;
	if (left.minute >= M_Minute_Max) {
		left.hour += left.minute / M_Minute_Max;
		left.minute %= M_Minute_Max;
	}
	else if (left.minute < 0) {
		left.hour += (left.minute - M_Minute_Max - 1) / M_Minute_Max;
		left.minute = (left.minute % M_Minute_Max + M_Minute_Max) % M_Minute_Max;
	}

	// 处理小时
	int days = 0;
	if (type == UTSCElementType::Day)
		days = i;
	else
		days = 0;
	if (type == UTSCElementType::Hour)
		left.hour += i;
	if (left.hour >= M_Hour_Max) {
		days += left.hour / M_Hour_Max;
		left.hour %= M_Hour_Max;
	}
	else if (left.hour < 0) {
		days += (left.hour - M_Hour_Max - 1) / M_Hour_Max;
		left.hour = (left.hour % M_Hour_Max + M_Hour_Max) % M_Hour_Max;
	}

	// 处理天数
	left.day += days;
	while (left.day > daysInMonth(left.year, left.month)) {
		left.day -= daysInMonth(left.year, left.month);
		if (++left.month > M_Month_Max) {
			left.month = 1;
			left.year++;
		}
	}
	while (left.day <= 0) {
		if (left.month - 1 < 1) {
			left.month = M_Month_Max;
			left.year--;
		}
		left.day += daysInMonth(left.year, left.month);
	}

		// 处理月份
		if (type == UTSCElementType::Month)
			left.month += i;

		while (left.month > M_Month_Max) {
			left.month -= M_Month_Max; // 如果月份大于12，调整为正确的月份
			left.year++;      // 年份增加
		}

		while (left.month < 1) {
			left.month += M_Month_Max; // 如果月份小于1，调整为正确的月份
			left.year--;      // 年份减少
		}

		// 确保日期有效性
		if (left.day > daysInMonth(left.year, left.month)) {
			left.day = daysInMonth(left.year, left.month); // 如果日期超过当前月份的天数，调整为当月最后一天
		}

		// 处理年份
		if (type == UTSCElementType::Year)
			left.year += i;

}

//得到TimeData时间点的左右时间点
void UTSCImpl::getNeighborTimeData(TimeData& left, TimeData& right, UTSCElementType type)
{
	getSingleNeighborTimeData(left, type, -1);
	getSingleNeighborTimeData(right, type, 1);
}

//TimeData中的值赋值给USTC时间编码
void UTSCImpl::timeData2UTSC(TimeData& left, TimeData& right, UTSCElementCode*& code, int signal)
{
	int i = 0;
	int  timeleftArray[7] = { left.year, left.month, left.day, left.hour, left.minute, left.second, left.millisecond };
	int  timerightArray[7] = { right.year, right.month, right.day, right.hour, right.minute, right.second, right.millisecond };
	for (int i = 0; i < 7; i++)
	{
		if (i == 0)     //年、月、日
		{
			if (signal == 1)
			{
				code[0].segmentCode[i].codes = timeleftArray[i] - M_TimeOrigin - 1;
				code[1].segmentCode[i].codes = timerightArray[i] - M_TimeOrigin - 1;
				code[0].signal = 1;
				code[1].signal = 1;
			}
			else
			{
				code[0].segmentCode[i].codes = M_TimeOrigin - timeleftArray[i] - 1;
				code[1].segmentCode[i].codes = M_TimeOrigin - timerightArray[i] - 1;
				code[0].signal = 0;
				code[1].signal = 0;
			}
		}
		else if (i == 1 || i == 2)
		{
			code[0].segmentCode[i].codes = timeleftArray[i] - 1;
			code[1].segmentCode[i].codes = timerightArray[i] - 1;
		}
		else
		{
			code[0].segmentCode[i].codes = timeleftArray[i];
			code[1].segmentCode[i].codes = timerightArray[i];
		}

	}
}

//得到GEO时间点的左或右时间点
void UTSCImpl::adjustGeoTime(std::vector<int>& time, int c)
{
	int number = time.size();
	if (number > 2)
	{
		time[number - 1] += c;
		if (time[number - 1] >= M_GeoTime_Max) {
			time[number - 2] += time[number - 1] / M_GeoTime_Max;
			time[number - 1] %= M_GeoTime_Max;
		}
		else if (time[number - 1] < 0) {
			time[number - 2] += (time[number - 1] - M_GeoTime_Max - 1) / M_GeoTime_Max;
			time[number - 1] = (time[number - 1] % M_GeoTime_Max + M_GeoTime_Max) % M_GeoTime_Max;
		}

		if (time[number - 2] >= M_GeoTime_Max) {
			time[number - 3] += time[number - 2] / M_GeoTime_Max;
			time[number - 2] %= M_GeoTime_Max;
		}
		else if (time[number - 2] < 0) {
			time[number - 3] += (time[number - 2] - M_GeoTime_Max - 1) / M_GeoTime_Max;
			time[number - 2] = (time[number - 2] % M_GeoTime_Max + M_GeoTime_Max) % M_GeoTime_Max;
		}
	}
	else if (number == 2)
	{
		time[number - 1] += c;
		if (time[number - 1] >= M_GeoTime_Max) {
			time[number - 2] += time[number - 1] / M_GeoTime_Max;
			time[number - 1] %= M_GeoTime_Max;
		}
		else if (time[number - 1] < 0) {
			time[number - 2] += (time[number - 1] - M_GeoTime_Max - 1) / M_GeoTime_Max;
			time[number - 1] = (time[number - 1] % M_GeoTime_Max + M_GeoTime_Max) % M_GeoTime_Max;
		}
	}
	else
	{
		time[number - 1] += c;
		if (time[number - 1] >= M_GeoTime_Max) {
			time.push_back(time[number - 1] / M_GeoTime_Max);
			time[number - 1] %= M_GeoTime_Max;
		}
	}
}

